package com.wyw.learning.offer;

/**
 * 复制一个链表，除了一个指向next，还有一个random指向随机一个节点
 *
 * @Author Mr Wu yewen.wu.china@gmail.com
 * @Date 2023/2/15 13:52
 */
public class Offer035 {
}

class solution{
//    public Node copyRandomList(Node head) {
//
//        if(head == null)
//            return null;
//
//        Map<Node, Node> map = new HashMap();
//
//        for(Node cur = head; cur != null; cur = cur.next) {
//            map.put(cur, new Node(cur.val));
//        }
//
//        for(Node cur = head; cur!=null; cur = cur.next) {
//            map.get(cur).next = map.get(cur.next);
//            map.get(cur).random = map.get(cur.random);
//        }
//
//        return map.get(head);
//
//    }

    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }

        //将拷贝节点放到原节点后面，例如1->2->3这样的链表就变成了这样1->1'->2->2'->3->3'
        for (Node node = head, copy = null; node != null; node = node.next.next) {
            copy = new Node(node.val);
            copy.next = node.next;
            node.next = copy;
        }

        //把拷贝节点的random指针安排上
        for (Node node = head; node != null; node = node.next.next) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
        }

        //分离拷贝节点和原节点，变成1->2->3和1'->2'->3'两个链表，后者就是答案
        Node newHead = head.next;
        for (Node node = head, temp = null; node != null && node.next != null;) {
            temp = node.next;
            node.next = temp.next;
            node = temp;
        }

        return newHead;
    }
}


class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

